package baseclass.d_list;


import utils.ListNode;

/**
 * 删除重复的节点1：{1,2,2,3,4,4,5,6,6}  ->  {1,3,5}
 *
 * @date 2020/2/28 22:39
 */
public class Code11_DeleteRepeatNode2_删除所有重复节点 {
    public static void deleteRepeat(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode cur = new ListNode(-1);
        ListNode pHead = head;
        boolean repeat = false;
        while (pHead != null) {
            ListNode next = pHead.next;
            //重复的点的尾巴
//            ListNode lastRepeat = pHead;
            //这一段判重
            while (next != null && (pHead.val == next.val)) {
//                lastRepeat = next;
                next = next.next;
                repeat = true;
            }
            if (repeat) {
                //之前的pHead  - lastRepeat 都是重复，GC。
                // 不用管pHead-lastRepeat也行,但是会造成内存泄漏
//                lastRepeat.next = null;
                //找到新的开始的头pHead,
                pHead = next;
                repeat = false;
            } else {
                //把cur和pHead连接起来
                cur.next = pHead;
                cur = cur.next;
                pHead = pHead.next;
            }
        }
        //考虑最后两个重复的情况，如1,4,4  cur = 1.其next没有置空
        cur.next = null;
    }

    //递归版本
    public static ListNode deleteDuplication2(ListNode pHead) {
        if (pHead == null || pHead.next == null) { // 只有0个或1个节点
            return pHead;
        }
        // 当前节点是重复节点
        if (pHead.val == pHead.next.val) {
            ListNode node = pHead.next;
            while (node != null && node.val == pHead.val) {
                // 跳过值与当前节点相同的全部节点，找到第一个与当前节点不同的节点
                node = node.next;
            }
            // 从第一个与当前结点不同的结点继续递归.
            // node一定不和phead等。也就是说相等的不会被加入链表。
            return deleteDuplication2(node);
        } else {
            // 保留当前节点，从下一个节点继续递归。
            // 并把当前节点返回给上一级。
            pHead.next = deleteDuplication2(pHead.next);
            return pHead;
        }

    }


    public static void main(String[] args) {
        ListNode pHead = new ListNode(0);
        pHead.next = new ListNode(1);
        pHead.next.next = new ListNode(2);
        pHead.next.next.next = new ListNode(3);
        pHead.next.next.next.next = new ListNode(3);
        pHead.next.next.next.next.next = new ListNode(4);
        pHead.next.next.next.next.next.next = new ListNode(5);
        pHead.next.next.next.next.next.next.next = new ListNode(5);
        deleteDuplication2(pHead);
        while (pHead != null) {
            System.out.print(pHead.val + " ");
            pHead = pHead.next;
        }
    }

}
